package algorithm.search;

//插值查找算法---要求数组有序
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] data = new int[100];
        for (int i = 1;i<=data.length;i++){
            data[i-1]=i;
        }
        System.out.println(insertValueSearch(data, 0, data.length - 1, 0));
    }

    public static int  insertValueSearch(int[] data,int left,int right,int key){
        int mid = left+(key-data[left])/(data[right]-data[left])*(right-left);
        if (left>right ||key<data[0] || key>data[data.length-1]){
            return -1;
        }
        if (key>data[mid]){
            return insertValueSearch(data,mid+1,right,key);
        }else if (key<data[mid]){
            return insertValueSearch(data,left,mid-1,key);
        }else {
            return mid;
        }
    }
}
